#include "graph.h"

Graph::Graph(const QRectF &r, QObject *parent)
	: QGraphicsScene(r, parent)
{
}

void Graph::addVertex(Vertex *v)
{
	if (m_adjacencyMap.contains(v))
		return;
	m_adjacencyMap.insert(v, QList<Edge *>());
	addItem(v);
}

void Graph::addEdge(Edge *e)
{
	if (!(e->u())||!(e->v()))
		return;
	if (!m_adjacencyMap.contains(e->u())) {
		m_adjacencyMap.insert(e->u(), QList<Edge *>());
		addItem(e->u());
	}
	if (!m_adjacencyMap.contains(e->v())) {
		m_adjacencyMap.insert(e->v(), QList<Edge *>());
		addItem(e->v());
	}
	if (m_adjacencyMap.value(e->u()).contains(e)||m_adjacencyMap.value(e->v()).contains(e))
		return;
	m_adjacencyMap[e->u()].append(e);
	m_adjacencyMap[e->v()].append(e);
	addItem(e);
}

Edge* Graph::edge(Vertex *u, Vertex* v)
{
	QList<Edge*> elist = edges(u);

	foreach(Edge* e, elist)
	{
		if(e->u() == u && e->v() == v)
		{
			return e;
		}else if(e->u() == v && e->v() == u)
		{
			return e;
		}
	}

	return NULL;
}

QList<Vertex *> Graph::vertices(const Vertex *v) const
{
	if (!v) {
		return m_adjacencyMap.keys();
	}
	QList<Vertex *> result;
	QList<Edge *> edges = m_adjacencyMap.value(const_cast<Vertex *>(v), QList<Edge *>());
	foreach (Edge *e, edges) {
		if (e->v() == v)
			result.append(e->u());
		else
			result.append(e->v());
	}
	return result;
}

QList<Edge *> Graph::edges(const Vertex *v) const
{
	if (v)
		return m_adjacencyMap.value(const_cast<Vertex *>(v), QList<Edge *>());
	QList<Edge *> result;
	for (QHash<Vertex *, QList<Edge *> >::const_iterator i = m_adjacencyMap.constBegin();
	i != m_adjacencyMap.constEnd(); ++i) {
		foreach (Edge *e, i.value()) {
			if (!result.contains(e))
				result.append(e);
		}
	}
	return result;
}

QString GraphFactory::generateName()
{
	QString result(currentName);
	int len = strlen(currentName);
	char *tmp = new char[len+2];
	strcpy(tmp, currentName);
	if (*(tmp+len-1) < 'Z') {
		++*(tmp+len-1);
	} else {
		int i;
		for (i = len-1; i >= 0; --i) {
			if (*(tmp+i) < 'Z') {
				++*(tmp+i);
				break;
			}
		}
		int z = ++i ? 0 : 1;
		for (i; i < len+z; ++i) {
			*(tmp+i) = 'A';
		}
		*(tmp+len+z) = '\0';
	}
	delete[] currentName;
	currentName = new char[len+2];
	strcpy(currentName, tmp);
	delete[] tmp;
	return result;
}

void GraphFactory::resetNameGenerator()
{
	if (currentName)
		delete currentName;
	currentName = new char[2];
	strcpy(currentName, "A");
}

Graph* GraphFactory::createGraph(int vertex_no, int lvl)
{
	Graph* g = new Graph();

	resetNameGenerator();

	QString nameA = generateName();
	QString nameB = generateName();

	Vertex* a = new Vertex(g, nameA);
	Vertex* b = new Vertex(g, nameB);

	g->addVertex(a);
	g->addVertex(b);

	g->addEdge(new Edge(g, a, b));

	for(int i = 0; i < vertex_no - 2; ++i)
	{
		int edge_cnt = lvl == 0 ? qrand() % (i +2) : lvl;

		QList<Vertex*> v = g->vertices();
		edge_cnt = edge_cnt > v.size() ? v.size() : edge_cnt;

		QString curr_ver_name = generateName();


		Vertex* new_v = new Vertex(g, curr_ver_name);

		g->addVertex(new_v);

		for(int j = 0; j < edge_cnt; ++j)
		{
			int n = (qrand() % (v.size()));
			g->addEdge(new Edge(g, new_v, v.at(n)));
			v.removeAt(n);
		}
	}

	fillGraph(g);

	return g;
}


void GraphFactory::fillGraph(Graph* g)
{
	QList<Vertex*> vlist = g->vertices();
	int v_cnt = vlist.size();

	QHash<int, Vertex*> mapping;

	for(int i = 0; i < v_cnt; ++i)
	{
		mapping.insert(i, vlist.at(i));
	}

	//int A = new A[v_cnt][v_cnt];



	for(int k = 0; k < v_cnt; ++k)
	{
		for(int i = 0; i < v_cnt; ++i)
		{
			for(int j = 0; j < v_cnt; ++j)
			{
				Vertex* vi = mapping[i];
				Vertex* vj = mapping[j];
				Vertex* vk = mapping[k];

				Edge* eij = g->edge(vi, vj);
				Edge* eik = g->edge(vi, vk);
				Edge* ejk = g->edge(vj, vk);

				if(eij == NULL)
				{
					eij = new VirtualEdge();
					eij->setU(vi);
					eij->setV(vj);
					g->addEdge(eij);
				}

				if(eik == NULL)
				{
					eik = new VirtualEdge();
					eik->setU(vi);
					eik->setV(vk);
					g->addEdge(eik);
				}

				if(ejk == NULL)
				{
					ejk = new VirtualEdge();
					ejk->setU(vj);
					ejk->setV(vk);
					g->addEdge(ejk);
				}

				if(eij->length() < eik->length() + ejk->length())
				{
					eij->clearEdges();
					((VirtualEdge*)eij)->addEdge(eik);
					((VirtualEdge*)eij)->addEdge(ejk);
				}
			}
		}
	}
}
